The deposition of information in a database server is actively used by the popularization of cloud computing. In the meantime, the leakage of confidential information such as personal information is also becoming a great social problem.
To securely deposit information in a database server while preventing the leakage of the information, searchable code technique that enables searching deposited data in an encrypted state is proposed. Information can be prevented from leaking to not only a third party on a channel but a database server manager by using a searchable code.
For the searchable code technique, various methods are proposed. A search using a searchable code is generally performed according to the following procedure.
(1) A client that deposits data calculates an index representing contents of the deposited data and secures it. In this case, securing means processing proper to a searchable code which makes it difficult to acquire the contents of the deposited data based upon the corresponding index. Hereinafter, the index that is secured is called secure index.
(2) The client encrypts the deposited data (hereinafter called encrypted data) and transmits it to a database server together with the secure index.
(3) The database server registers a pair of the encrypted data and the secure index in a database.
(4) The search client that searches the data calculates a trapdoor of a keyword (a search query) to be searched. In this case, the trapdoor means information for a search and especially, means the secure keyword for a search included in the search query.
(5) The search client transmits the trapdoor to the database server.
(6) The database server searches data that hits the search query by collating the secure index registered in the database and the trapdoor in a procedure proper to the searchable code.
(7) The database server transmits encrypted data corresponding to the hit secure index and the like to the search client.
(8) The search client specifies a client that deposits data based upon a received search result and shares a decrypting key with the corresponding client.
(9) The search client decrypts the encrypted data received from the database server using the shared key.
As the deposited data is encrypted, it is substantially impossible that a database server manager decrypts the deposited data. In addition, since the index is secured, it is difficult to extract contents of the deposited data based upon the index. Further, since the search query is converted to the trapdoor, the possibility of the leakage of the search query is also low. Further, since it is also difficult to determine whether different secure indexes include the same keyword or not, unjust attack such as frequency analysis that estimates an unciphered text based upon the frequency of appearance of a word can be prevented. As described above, information can be substantially prevented from leaking not only to a third party on a channel but to the database server manager and the like by using searchable code technique.
For the searchable code technique, Non-patent Literature 1 and Non-patent Literature 2 are known for example. These methods adopt a random encryption method in which an unciphered text and its encrypted text have the complex correlation of 1 to m and which is securer than a deterministic encryption method in which an unciphered text and its encrypted text have the simple correlation of 1 to 1. These methods are relatively secure from attack such as frequency analysis.
In addition, Non-patent Literature 3, Non-patent Literature 4 and Patent Literature 1 are also known. In methods disclosed in Non-patent Literature 3 and Non-patent Literature 4, tolerance to attack such as frequency analysis is also applied by utilizing Bloom filter which is one of random data structure. In a method disclosed in Patent Literature 1, tolerance to attack such as frequency analysis is also applied by using Fuzzy Vault Scheme for realizing fuzzy collation between clusters using an error-correcting code.
The techniques disclosed in Non-patent Literatures 1 to 4 and Patent Literature 1 guarantee security from frequency analysis by utilizing random encryption, random data structure, fuzzy collation technique and the like. For a concrete example, when plural data pieces including a keyword “cloud” are deposited in the database server, a corresponding secure index is different for each deposited data piece. Further, it is difficult to determine that the secure indexes include the same keyword “cloud”. Furthermore, even if a search is made based upon “cloud”, it is difficult to guess a search query “cloud” based upon a trapdoor. Therefore, even if a fact that the search query is hit is known, the database server manager cannot substantially know whether the secure index includes “cloud” or not.